package com.searchlist.skiplist;

import java.util.ArrayList;
import java.util.Random;
import java.util.Stack;

import com.searchtree.main.Utilities;

public class SkipList
{
	private static SkipList skipList;
	private Stack<SkipListNode> stackNode;
	private ArrayList<SkipListRow> rows = new ArrayList<SkipListRow>();
	
	public static SkipList getInstance()
	{
		if (skipList == null)
		{
			skipList = new SkipList();
		}
		
		return skipList;
	}
	
	public SkipList()
	{
		this.addNewRow();
		this.addNewRow();
	}
	
	public void insert(String key)
	{
		SkipListNode currentNode = skipList.search(key);
		// No double key values allowed
		if (!currentNode.getKey().equals(key))
		{
			// Add the node to the bottom list
			SkipListNode belowNewNode = new SkipListNode(key);
			this.addNodeToRow(currentNode, belowNewNode);
			
			// Random decision if the value is added to list above.
			Random r = new Random();
			while(r.nextBoolean())
			{
				SkipListNode aboveNewNode = new SkipListNode(key);
				if (!stackNode.empty())
				{
					this.addNodeToRow(stackNode.pop(), aboveNewNode);
				}
				else 
				{
					// StackNode is empty, so a new row needs to be created with newNode in it.
					SkipListRow newRow = this.addNewRow();
					this.addNodeToRow(newRow.getFirstNode(), aboveNewNode);
				}
				
				aboveNewNode.setBelowNode(belowNewNode);
				belowNewNode = aboveNewNode;
			}
		}
	}
	
	public SkipListNode search(String key)
	{
		int row = this.rows.size() - 1;
		stackNode = new Stack<SkipListNode>();
		
		// Start at the top left position.
		SkipListRow currentRow   = this.getRow(row);
		SkipListNode currentNode = currentRow.getFirstNode();
		
		while (row > 0)
		{
			// Safe the node where we went to a lower row
			stackNode.push(currentNode);
			row--;
			
			currentRow  = this.getRow(row);
			currentNode = currentNode.getBelowNode();
			
			while (currentNode.getNextNode().getKey() != "infinite" && 
				   Utilities.compareStringValues(currentNode.getNextNode().getKey(), key) != 1)
			{
				currentNode = currentNode.getNextNode();
			}
		}
		
		return currentNode;
	}
	
	public String searchKey(String key)
	{
		SkipListNode skn = search(key);
		if(skn.getKey().equals(key))
			return search(key).toString();
		else
			return "Key " + key +" not in this skiplist";
	}
	
	public ArrayList<SkipListRow> getRows()
	{
		return this.rows;
	}
	
	public SkipListRow getRow(int row)
	{
		return rows.get(row);
	}
	
	private void addNodeToRow(SkipListNode currentNode, SkipListNode newNode)
	{
		newNode.setPreviousNode(currentNode);
		newNode.setNextNode(currentNode.getNextNode());
		
		currentNode.getNextNode().setPreviousNode(newNode);
		currentNode.setNextNode(newNode);
	}
	
	private SkipListRow addNewRow()
	{
		SkipListRow newRow = new SkipListRow();
		if (this.rows.size() > 0)
		{
			newRow.getFirstNode().setBelowNode(this.getRow(this.rows.size() - 1).getFirstNode());
			newRow.getLastNode().setBelowNode(this.getRow(this.rows.size() - 1).getLastNode());
		}
		
		rows.add(newRow);
		
		return newRow;
	}
}